package com.hss.tree;

/**
 * https://segmentfault.com/a/1190000008850005
 */
public class TreeTest {
    public static 	int[] a = { 49, 38, 65, 97, 23, 76, 1, 5, 8, 2, 0, 13, -1,34 ,400,-230,-4000};

    public static void main(String[] args) {
        Root root = null;
        for (int i=0;i <a.length;i++){
            root =  createTree(root, a[i]);

        }
//        midTraverseTree(root.root);

        System.out.println("height = "+getHeight(root.root));

        System.out.println("max = " + getMax(root.root));
    }

    public static Root createTree(Root root, int value){
        if (root == null ){
            root  = new Root();
            root.root = new Node(value);

        }else {
            Node tmpNode = root.root;


            while (tmpNode != null){
                if (value > tmpNode.value){

                    if (tmpNode.right ==null){
                        tmpNode.right = new Node(value);
                        break;
                    }

                    tmpNode = tmpNode.right;
                }else {
                    if (tmpNode.left ==null){
                        tmpNode.left = new Node(value);
                        break;
                    }
                    tmpNode = tmpNode.left;

                }
            }
        }

        return root;
    }


    public static void preTraverseTree(Node root){
        if (root == null){
            return;
        }
        System.out.println(root.value);
        preTraverseTree(root.left);
        preTraverseTree(root.right);

    }

    public static void midTraverseTree(Node root){
        if (root == null){
            return;
        }
        midTraverseTree(root.left);
        System.out.println(root.value);
        midTraverseTree(root.right);
    }
    public static void afterTraverseTree(Node root){
        if (root == null){
            return;
        }
        afterTraverseTree(root.left);
        afterTraverseTree(root.right);
        System.out.println(root.value);
    }

    public static int  getHeight(Node root){
        int height = 0;
        if (root !=null ){
            int left = getHeight(root.left);
            int right = getHeight(root.right);

            return Math.max(left,right)+1;
        }
        return height;
    }

    public static int getMax(Node root){
        int max = 0;
        if (root == null){
            return  -1;
        }
        int left = getMax(root.left);

        int right = getMax(root.right);

        max = Math.max(left,right);
        max = Math.max(max,root.value);

        return max;
    }

    // 求二叉树第k层的节点个数
    int getKNoteCount(Node root, int k){
        if (root == null || k <1){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKNoteCount(root.left,k-1)+ getKNoteCount(root.right,k-1);
    }

    //7 判断两棵二叉树是否结构相同
    boolean StructureCmp(Node root1, Node root2){
        if (root1 ==null && root2 == null){
            return true;
        }else if (root1 ==null || root2 == null){
            return  false;
        }
        boolean leftValure = StructureCmp(root1.left,root2.left);
        boolean rightValure = StructureCmp(root1.right,root2.right);
        return  leftValure && rightValure;
    }

    //求二叉树的镜像
    void mirro (Node  node){
        if (node == null){
            return;
        }
        Node temp = node.left;
        node.left = node.right;
        node.right= temp;
        mirro(node.left);
        mirro(node.right);
    }
    //求两个节点的最低公共祖先节点
    Node findLCA(Node node, Node target1, Node target2){
        if (node == null){
            return null;
        }
        if (target1 == node || target2 == node){
            return  node;
        }
        Node left = findLCA(node.left, target1, target2);
        Node right = findLCA(node.right, target1, target2);
        if (left !=null &&  right != null)//分别再左右子树
            return node;
        return left ==null? right :left;
    }

    //求任意两节点距离
    //首先找到两个节点的LCA，然后分别计算LCA与它们的距离，最后相加即可。
    //找到层级
    int findLevel(Node node, Node target){
        if (node == null){
            return  -1;
        }
        if (node == target){
            return  0;
        }
        int level = findLevel(node.left, target);
        if (level == -1){
            level = findLevel(node.right, target);//如果左子树没找到，在右子树找
        }
        if (level != -1){ //找到了，回溯
            return  level+1;
        }
        return  -1;
    }
    //求任意两节点距离
    int DistanceNodes(Node  node, Node  target1, Node  target2){
        Node lca = findLCA(node, target1,target2);
        int level1 =findLevel(lca, target1);
        int level2 = findLevel(lca, target2);
        return level1 + level2;
    }
}
